"""
给定nums数组与queires操作
每次操作将nums[a, b]范围内的元素最多减c
问最少需要前几个操作使得数组全部非正
显然二分
"""
import bisect
from typing import List
class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        N = len(nums)
        diff = [0 for i in range(N)]
        diff[0] = nums[0]
        for i in range(1, N):
            diff[i] = nums[i] - nums[i - 1]

        def check(k): # 可以直接在0数组上做操作，这样就不用每次还原差分数组
            for i in range(0, k):
                a, b, c = queries[i]
                diff[a] -= c
                if b + 1 < len(nums): diff[b + 1] += c
            ans = True
            s = 0
            for ai in diff:
                s += ai
                if s > 0: ans = False
            for i in range(0, k):
                a, b, c = queries[i]
                diff[a] += c
                if b + 1 < len(nums): diff[b + 1] -= c
            return ans

        N = len(queries)
        # 首先定义数组A[0， 1, 2, ..., N]
        # 然后定义check函数使得数组前半段都返回0，后半段都返回1
        # 然后在数组上二分找到最左边的1的位置，记作p，则A[p]就是满足条件的最小值
        ans = bisect.bisect_left(range(0, N + 1), 1, key=lambda x: 1 if check(x) else 0)
        # return ans
        return ans if ans <= N else -1